#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"

//性能对比
void TestOp()
{
    srand((unsigned int)time(NULL));
    int N = 1000000;
    //申请空间
    int* a1 = (int*)malloc(sizeof(int) * N);
    int* a2 = (int*)malloc(sizeof(int) * N);
    int* a3 = (int*)malloc(sizeof(int) * N);
    int* a4 = (int*)malloc(sizeof(int) * N);
    int* a5 = (int*)malloc(sizeof(int) * N);
    int* a6 = (int*)malloc(sizeof(int) * N);
    int* a7 = (int*)malloc(sizeof(int) * N);
    int* a8 = (int*)malloc(sizeof(int) * N);
    int* a9 = (int*)malloc(sizeof(int) * N);
    int* a10 = (int*)malloc(sizeof(int) * N);
    if (!a1 || !a2 || !a3 || !a4 || !a5 || !a6 || !a7 || !a8 || !a9 || !a10) exit(1);
    //申请的空间内填入随机值
    for (int i = 0; i < N; i++)
    {
        a1[i] = rand();
        a2[i] = a1[i];
        a3[i] = a1[i];
        a4[i] = a1[i];
        a5[i] = a1[i];
        a6[i] = a1[i];
        a7[i] = a1[i];
        a8[i] = a1[i];
        a9[i] = a1[i];
        a10[i] = a1[i];
    }

    //计算时间
    int begin1 = clock();
    //InsertSort(a1,N);
    int end1 = clock();

    int begin2 = clock();
    ShellSort(a2, N);
    int end2 = clock();

    int begin3 = clock();
    //SelectSort(a3,N);
    int end3 = clock();

    int begin4 = clock();
    HeapSort(a4, N);
    int end4 = clock();

    int begin5 = clock();
    //BubbleSort(a5,N);
    int end5 = clock();

    int begin6 = clock();
    QuickSort(a6, N);
    int end6 = clock();

    int begin7 = clock();
    QuickSortNonR(a7, N);
    int end7 = clock();

    int begin8 = clock();
    MergerSort(a8,N);
    int end8 = clock();

    int begin9 = clock();
    MergerSortNonR(a9, N);
    int end9 = clock();

    int begin10 = clock();
    CountSort(a10, N);
    int end10 = clock();

    printf("InsertSort:%d\n", end1 - begin1);
    printf("ShellSort:%d\n", end2 - begin2);
    printf("SlelectSort:%d\n", end3 - begin3);
    printf("HeapSort:%d\n", end4 - begin4);
    printf("BubbleSort:%d\n", end5 - begin5);
    printf("QuickSort:%d\n", end6 - begin6);
    printf("QuickSortNonr:%d\n", end7 - begin7);
    printf("MergerSort:%d\n", end8 - begin8);
    printf("MergerSortNonR:%d\n", end9 - begin9);
    printf("CountSort:%d\n", end10 - begin10);

    free(a1);
    free(a2);
    free(a3);
    free(a4);
    free(a5);
    free(a6);
    free(a7);
    free(a8);
    free(a9);
    free(a10);
}

void InsertSortTest()
{
    int arr[] = { 8,3,10,2,9,7,6,1,5,4 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    PrintArr(arr, sz);
    InsertSort(arr, sz);
    PrintArr(arr, sz);
}

void ShellSortTest()
{
    int arr[] = { 8,3,10,2,9,7,6,1,5,4 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    PrintArr(arr, sz);
    ShellSort(arr, sz);
    PrintArr(arr, sz);
}

void SelectSortTest()
{
    // int arr[] = {8,3,10,2,9,7,6,1,5,4};
    //int arr[] = {8,3,10,2,9,7,6,1,5,4,12,55,64,35,75,2,22};
    int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    PrintArr(arr, sz);
    SelectSort(arr, sz);
    PrintArr(arr, sz);
}

void HeapSortTest()
{
    int arr[] = { 8,3,10,2,9,7,6,1,5,4 };
    //int arr[] = {8,3,10,2,9,7,6,1,5,4,12,55,64,35,75,2,22};
    //int arr[] = {10,9,8,7,6,5,4,3,2,1};
    int sz = sizeof(arr) / sizeof(arr[0]);
    PrintArr(arr, sz);
    HeapSort(arr, sz);
    PrintArr(arr, sz);
}

void BubbleSortTest()
{
    int arr[] = { 8,3,10,2,9,7,6,1,5,4 };
    //int arr[] = {8,3,10,2,9,7,6,1,5,4,12,55,64,35,75,2,22};
    //int arr[] = {10,9,8,7,6,5,4,3,2,1};
    int sz = sizeof(arr) / sizeof(arr[0]);
    PrintArr(arr, sz);
    BubbleSort(arr, sz);
    PrintArr(arr, sz);
}

void QuickSortTest()
{
    int arr[] = { 8,3,10,2,9,7,6,1,5,4,2 };
    //int arr[] = {8,3,10,2,9,7,6,1,5,4,12,55,64,35,75,2,22};
    //int arr[] = {10,9,8,7,6,5,4,3,2,1};
    int sz = sizeof(arr) / sizeof(arr[0]);
    PrintArr(arr, sz);
    QuickSortNonR(arr, sz);
    PrintArr(arr, sz);
}

void MergerSortTest()
{
    int arr[] = { 8,3,10,2,9,7,6,1,5,4 };
    //int arr[] = {8,3,10,2,9,7,6,1,5,4,12,55,64,35,75,2,22};
    //int arr[] = {10,9,8,7,6,5,4,3,2,1};
    int sz = sizeof(arr) / sizeof(arr[0]);
    PrintArr(arr, sz);
    MergerSort(arr, sz);
    PrintArr(arr, sz);
}

void MergerSortNonRTest()
{
    int arr[] = { 8,3,10,2,9,7,6,1,5,4 };
    //int arr[] = {8,3,10,2,9,7,6,1,5,4,12,55,64,35,75,2,22};
    //int arr[] = {10,9,8,7,6,5,4,3,2,1};
    int sz = sizeof(arr) / sizeof(arr[0]);
    PrintArr(arr, sz);
    MergerSortNonR(arr, sz);
    PrintArr(arr, sz);
}
void CountSortTest()
{
    //int arr[] = { 8,3,10,2,9,7,6,1,5,4 };
    //int arr[] = {8,3,10,2,9,7,6,1,5,4,12,55,64,35,75,2,22};
    //int arr[] = {10,9,8,7,6,5,4,3,2,1};
    int arr[] = { 10,14,11,13,20,17,18,14,11 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    PrintArr(arr, sz);
    CountSort(arr, sz);
    PrintArr(arr, sz);
}

int main()
{
    //BubbleSortTest();
    //QuickSortTest();
    //MergerSortNonRTest();
    //CountSortTest();
    TestOp();
    return 0;
}


